//目录：
// 1.二分查找 binarySearch  
// 2.数组去重 去重unique  unique2
// 3.统计字符串出现最多的字母 getMaxAppearNum
// 4.斐波那契数列--递归 getFibonacci
// 5.合并两个已排序数组 mergeSortedArray


// 1.二分查找算法（建立在已经排好序的情况下）
function binarySearch(arr, data) {
    var end = arr.length - 1,
        start = 0;

    while (start <= end) {
        var middle = Math.floor((start + end) / 2);
        if (arr[middle] > data) {
            end = middle - 1;
        } else if (arr[middle] < data) {
            start = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;

}

// var arr = [1, 2, 3, 4, 5, 6];
// console.log("二分查找算法（建立在已经排好序的情况下）:"+binarySearch(arr, 3));

// 2.去重1
//  去掉一组整型数组重复的值
// 题目如下输入: [3,13,24,11,11,14,1,2]
// 输出: [3,13,24,11,14,2]
// 需要去掉重复的11 和 1 这两个元素。
function unique(arr) {
    let hashTable = {};
    let data = [];
    for (let i = 0, l = arr.length; i < l; i++) {
        if (!hashTable[arr[i]]) {
            hashTable[arr[i]] = true;
            data.push(arr[i]);
        }
    }
    return data
}
// console.log("去重1:"+unique([3,13,24,11,11,14,1,2]));
// 去重2
function unique2(arr) {
    let data = [];
    for (let i = 0, l = arr.length; i < l; i++) {
        if (data.indexOf(arr[i]) == -1) {
            data.push(arr[i]);
        }
    }
    return data
}
// console.log("去重2:"+unique2([3,13,24,11,11,14,1,2]));


// 3.统计字符串出现最多的字母

function getMaxAppearNum(str) {
    var hash = {},
        maxstr, max = 1;
    for (var i = 0; i < str.length; i++) {
        if (!hash[str[i]]) {
            hash[str[i]] = 1;
        } else {
            hash[str[i]]++;
        }
        if (hash[str[i]] > max) {
            max = hash[str[i]];
            maxstr = str[i];
        }
    }
    return maxstr;
}

// var str = 'abcdeffggghhhhiiiii';
// console.log("统计字符串出现最多的字母:"+getMaxAppearNum(str));


// 4.斐波那契数列--递归
// 斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。
function getFibonacci(n) {
    var fibarr = [];
    var i = 0;
    while (i < n) {
        if (i <= 1) {
            fibarr.push(i);
        } else {
            fibarr.push(fibarr[i - 1] + fibarr[i - 2])
        }
        i++;
    }
    return fibarr;
}
//   console.log("斐波那契数列:"+getFibonacci(9));

// 5.合并两个已排序数组
function mergeSortedArray(a, b) {
    var merge = [];
    var i = 0,
        j = 0;
    var k = 0;
    while (i < a.length || j < b.length) {
        if (i == a.length || (j != b.length && a[i] > b[j])) {
            merge[k++] = b[j++];
        } else {
            merge[k++] = a[i++];
        }
    }
    return merge;
}
// console.log("合并两个已排序数组:" + mergeSortedArray([1, 3, 6], [2, 4, 5]));